package com.zac.coroutine.algorithm.leetcode.others

/**
 * author zac
 * date 2024/11/21
 * 118. 杨辉三角
 * 给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
 * 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
 */
object YangHuiTriangle2 {
    //杨辉三角第n行第m个数的公式为组合数
    //C(n−1,m−1)

    // 递推公式:
    /**
     * C(n,k)=C(n,m−1)×(n−m+1)/m
     */

    @JvmStatic
    fun main(args: Array<String>) {
        getRow1(3).forEach {
            print("$it,")
        }
    }

    fun getRow1(rowIndex: Int): List<Int?> {
        var n = 1
        val list = ArrayList<Int>()
        list.add(n)
        for (i in 1 until rowIndex + 1) {
            if (i > rowIndex / 2) {
                if (i == rowIndex) {
                    list.add(1)
                } else {
                    list.add(list[rowIndex - i])
                }
            } else {
                list.add(((list.last().toLong() * (rowIndex - i + 1)) / i).toInt())
            }
        }
        return list
    }


    /**
     * 算法没错,但是超出了Int的范围,而且低效
     */
    fun getRow(rowIndexFromZero: Int): List<Int?> {
        val rowIndex = rowIndexFromZero + 1
        val list = ArrayList<Int>()
        if (rowIndex == 1) {
            list.add(1)
            return list
        }
        val top = cm(rowIndex - 1)

        for (m in 1..rowIndex) {
            val bottomLeft = cm(m - 1)
            val bottomRight = cm(rowIndex - m)
            val bottom = bottomLeft * bottomRight
            list.add(top / bottom)
        }

        return list
    }

    // x的阶乘
    fun cm(x: Int): Int {
        var result = 1
        for (i in 1 until x + 1) {
            if (i == 1) {
                result = i
            } else {
                result *= i
            }
        }
        return result
    }
}
